﻿/**
<code>
  <author name="Zealic" email="zealic(at)gmail.com" type="Creator"/>
</code>
**/
using System;
using System.Linq.Expressions;
using System.Text;
using System.ComponentModel;
using System.Reflection;


namespace Zealib
{
    /// <summary>
    /// Compute expression, support "+"、"-"、"*"、"/"、"%" operation, bracket priority and decimal compute.
    /// Support condition expression, condition operation have "&lt;"、"&lt;="、"&gt;"、"&gt;="、"==", See example:
    /// <code>
    ///		"1 >= 2 ? 10 : 20"
    /// </code>
    /// Result is 20.
    /// </summary>
    public class ComputeExpression
    {
        private class Parser<T>
        {
            #region Private members

            private readonly MethodInfo m_ParseMethod;
            private readonly Func<string, T> m_ParseFunc;
            private readonly ComputeExpression m_Parent;

            private enum NodeType
            {
                None = 0,
                Digit,
                Operation,
                Expression,
                StringExpression,
                Condition,
            }

            private enum OpCodes
            {
                None = 0,

                Add,
                Subtract,
                Multiply,
                Divide,
                Modulo,

                // Conditions
                Equal,
                NotEqual,
                GreaterThan,
                LessThan,
                GreaterThanOrEqual,
                LessThanOrEqual,

                QuestionMark,
                Colon,
            }

            private class Node
            {
                private Node _Prev, _Next;

                public NodeType Type { get; set; }
                public string Text { get; set; }
                public OpCodes OpCode { get; set; }

                public Expression Expression { get; set; }

                public Node Prev
                {
                    get { return _Prev; }
                    set
                    {
                        _Prev = value;
                        if (value != null)
                        {
                            value._Next = this;
                        }
                    }
                }
                public Node Next
                {
                    get { return _Next; }
                    set
                    {
                        _Next = value;
                        if (value != null)
                        {
                            value._Prev = this;
                        }
                    }
                }

                public Node FirstNode
                {
                    get
                    {
                        Node node = this;
                        while (node.Prev != null)
                        {
                            node = node.Prev;
                        }
                        return node;
                    }
                }

                public Node LastNode
                {
                    get
                    {
                        Node node = this;
                        while (node != null)
                        {
                            node = node.Next;
                        }
                        return node;
                    }
                }

                public bool IsAlone
                {
                    get
                    {
                        return Next == null && Prev == null;
                    }
                }

                public override string ToString()
                {
                    string next = "";
                    if (Next != null)
                        next = Next.ToString();
                    if (Expression != null)
                        return Expression + next;
                    if (Type == NodeType.Digit ||
                        Type == NodeType.Operation ||
                        Type == NodeType.Condition)
                        return Text + next;
                    if (Type == NodeType.StringExpression)
                        return string.Format("({0}){1}", Text, next);
                    if (Type == NodeType.Condition)

                        if (string.IsNullOrEmpty(Text))
                            return Text + next;

                    return base.ToString() + next;
                }

            }

            private class ConditionContext
            {
                public static bool TryLoad(Node node, out ConditionContext cc)
                {
                    var ret = new ConditionContext { Condition = node };
                    if (ret.Condition.Prev != null && ret.Condition.Next != null)
                    {
                        ret.LeftValue = ret.Condition.Prev;
                        ret.RightValue = ret.Condition.Next;
                        if (ret.RightValue.Next != null)
                        {
                            ret.QuestionMark = ret.RightValue.Next;
                            if (ret.QuestionMark.Next != null)
                            {
                                ret.TrueValue = ret.QuestionMark.Next;
                                if (ret.TrueValue.Next != null)
                                {
                                    ret.Colon = ret.TrueValue.Next;
                                    if (ret.Colon.Next != null)
                                    {
                                        ret.FalseValue = ret.Colon.Next;
                                        cc = ret;
                                        return true;
                                    }
                                }
                            }
                        }
                    }
                    cc = null;
                    return false;
                }

                public Node Condition { get; set; }
                public Node QuestionMark { get; set; }
                public Node Colon { get; set; }
                public Node LeftValue { get; set; }
                public Node RightValue { get; set; }
                public Node TrueValue { get; set; }
                public Node FalseValue { get; set; }
            }

            #endregion

            public Parser(ComputeExpression parent)
            {
                m_Parent = parent;
                if (!typeof(T).IsPrimitive)
                {
                    m_ParseMethod = typeof(T).GetMethod("Parse", BindingFlags.Public | BindingFlags.Static, null, new[] { typeof(string) }, null);
                    m_ParseFunc = (Func<string, T>)Delegate.CreateDelegate(typeof(Func<string, T>), m_ParseMethod);
                }
            }

            #region Build expression
            public Expression Parse()
            {
                return ParseText(m_Parent.ExpressionText);
            }

            private Expression ParseText(string strExp)
            {
                Node nodes = AnalyseNodes(strExp);
                ProcessStringExpression(nodes);
                ProcessDigit(nodes);
                nodes = ProcessUaryOperation(nodes);
                nodes = ProcessBinaryOperation(nodes);
                nodes = ProcessCondition(nodes);
                if (!nodes.IsAlone) throw new InvalidOperationException();
                return nodes.FirstNode.Expression;
            }

            private void ProcessStringExpression(Node node)
            {
                while (node != null)
                {
                    if (node.Type == NodeType.StringExpression)
                    {
                        node.Expression = ParseText(node.Text);
                        node.Type = NodeType.Expression;
                    }
                    node = node.Next;
                }
            }

            private void ProcessDigit(Node nodes)
            {
                while (nodes != null)
                {
                    if (nodes.Type == NodeType.Digit)
                    {
                        if (typeof(T).IsPrimitive)
                        {
                            nodes.Expression = Expression.Constant(Convert.ChangeType(nodes.Text, typeof(T)), typeof(T));
                        }
                        else
                        {
                            nodes.Expression = Expression.Constant(m_ParseFunc(nodes.Text));
                        }
                        nodes.Type = NodeType.Expression;
                    }
                    nodes = nodes.Next;
                }
            }

            private Node ProcessUaryOperation(Node nodes)
            {
                Node result = nodes;
                Node node = FindUaryOperation(nodes.FirstNode);

                while (node != null)
                {
                    if (node.OpCode == OpCodes.Add)
                        node.Expression = Expression.UnaryPlus(node.Next.Expression);
                    else if (node.OpCode == OpCodes.Subtract)
                        node.Expression = Expression.Negate(node.Next.Expression);
                    node.Next = node.Next.Next;
                    node.OpCode = OpCodes.None;
                    node.Type = NodeType.Expression;
                    result = node;

                    node = FindUaryOperation(node.FirstNode);
                }

                return result;
            }

            private Node ProcessBinaryOperation(Node nodes)
            {
                Node result = nodes;
                Node node = FindBinaryOperation(nodes.FirstNode);

                while (node != null)
                {
                    node.Expression = Expression.MakeBinary(GetExpType(node.OpCode), node.Prev.Expression, node.Next.Expression);
                    node.Prev = node.Prev.Prev;
                    node.Next = node.Next.Next;
                    node.Type = NodeType.Expression;
                    result = node;

                    node = FindBinaryOperation(node.FirstNode);
                }

                return result;
            }

            private Node ProcessCondition(Node nodes)
            {
                Node result = nodes;
                Node node = FindCondition(nodes.FirstNode);

                while (node != null)
                {
                    ConditionContext cc;
                    if (ConditionContext.TryLoad(node, out cc))
                    {
                        Expression testExp;
                        if (node.OpCode == OpCodes.LessThan)
                        {
                            testExp = Expression.LessThan(cc.LeftValue.Expression, cc.RightValue.Expression);
                        }
                        else if (node.OpCode == OpCodes.GreaterThan)
                        {
                            testExp = Expression.GreaterThan(cc.LeftValue.Expression, cc.RightValue.Expression);
                        }
                        else if (node.OpCode == OpCodes.LessThanOrEqual)
                        {
                            testExp = Expression.LessThanOrEqual(cc.LeftValue.Expression, cc.RightValue.Expression);
                        }
                        else if (node.OpCode == OpCodes.GreaterThanOrEqual)
                        {
                            testExp = Expression.GreaterThanOrEqual(cc.LeftValue.Expression, cc.RightValue.Expression);
                        }
                        else if (node.OpCode == OpCodes.Equal)
                        {
                            testExp = Expression.Equal(cc.LeftValue.Expression, cc.RightValue.Expression);
                        }
                        else if (node.OpCode == OpCodes.NotEqual)
                        {
                            testExp = Expression.NotEqual(cc.LeftValue.Expression, cc.RightValue.Expression);
                        }
                        else
                        {
                            throw GetFormatException();
                        }

                        Node ifTrue = cc.TrueValue;
                        Node ifFalse = cc.FalseValue;
                        node.Expression = Expression.Condition(testExp, ifTrue.Expression, ifFalse.Expression);
                        node.Prev = cc.LeftValue.Prev;
                        node.Next = cc.FalseValue.Next;
                        node.OpCode = OpCodes.None;
                        node.Type = NodeType.Expression;
                        result = node;
                    }
                    node = FindBinaryOperation(node.FirstNode);
                }

                return result;
            }

            private ExpressionType GetExpType(OpCodes code)
            {
                switch (code)
                {
                    // Uary and binary
                    case OpCodes.Multiply: return ExpressionType.MultiplyChecked;
                    case OpCodes.Divide: return ExpressionType.Divide;
                    case OpCodes.Modulo: return ExpressionType.Modulo;
                    case OpCodes.Add: return ExpressionType.AddChecked;
                    case OpCodes.Subtract: return ExpressionType.SubtractChecked;
                }
                throw new NotSupportedException();
            }

            private Node FindUaryOperation(Node node)
            {
                Node current = node;
                while ((current = FindNode(current, new[] { OpCodes.Add, OpCodes.Subtract })) != null)
                {
                    if (current.Prev != null &&
                        current.Prev.Type == NodeType.Operation)
                    {
                        return current;
                    }
                    current = current.Next;
                }
                return null;
            }

            private Node FindBinaryOperation(Node node)
            {
                Func<Node, OpCodes[], Node> findOp =
                    delegate(Node n, OpCodes[] codes)
                    {
                        Node current = n;
                        while ((current = FindNode(current, codes)) != null)
                        {
                            if (current.Prev != null &&
                                current.Prev.Type == NodeType.Expression &&
                                current.Next != null &&
                                current.Next.Type == NodeType.Expression)
                            {
                                return current;
                            }
                            current = current.Next;
                        }
                        return current;
                    };

                return (findOp(node, new[] { OpCodes.Multiply, OpCodes.Divide, OpCodes.Modulo }) ??
                          findOp(node, new[] { OpCodes.Add, OpCodes.Subtract }));
            }

            private Node FindCondition(Node node)
            {
                Func<Node, OpCodes[], Node> findCond =
                    delegate(Node n, OpCodes[] codes)
                    {
                        Node current = n;
                        while ((current = FindNode(current, codes)) != null)
                        {
                            ConditionContext cc;
                            if (ConditionContext.TryLoad(current, out cc))
                            {
                                if (cc.LeftValue.Type == NodeType.Expression &&
                                    cc.RightValue.Type == NodeType.Expression &&
                                    cc.QuestionMark.OpCode == OpCodes.QuestionMark &&
                                    cc.TrueValue.Type == NodeType.Expression &&
                                    cc.Colon.OpCode == OpCodes.Colon &&
                                    cc.FalseValue.Type == NodeType.Expression) return current;
                            }
                            current = current.Next;
                        }
                        return current;
                    };

                return (findCond(node, new[] { OpCodes.LessThan, OpCodes.GreaterThan, OpCodes.LessThanOrEqual, OpCodes.GreaterThanOrEqual }) ??
                        findCond(node, new[] { OpCodes.Equal, OpCodes.NotEqual }));
            }

            #endregion

            #region Analyse expression
            private Node AnalyseNodes(string strExp)
            {
                char c;
                Node current = null;
                strExp = new StringBuilder(strExp).Replace(" ", string.Empty).ToString();

                for (int i = 0; i < strExp.Length; i++)
                {
                    c = strExp[i];
                    if (current == null)
                    {
                        current = new Node();
                    }
                    else
                    {
                        Node node = new Node();
                        node.Prev = current;
                        current = node;
                    }

                    if (IsDigit(c))
                    {
                        int origin = i;
                        int len = 0;
                        while (true)
                        {
                            c = strExp[i];
                            if (!IsDigit(c))
                            {
                                i--;
                                break;
                            }
                            i++;
                            len++;
                            if (i >= strExp.Length) break;
                        }
                        current.Text = strExp.Substring(origin, len);
                        current.Type = NodeType.Digit;
                    }
                    else switch (c)
                        {
                            case '*':
                            case '/':
                            case '%':
                            case '+':
                            case '-':
                                current.Text = c.ToString();
                                current.OpCode = GetOpCode(c.ToString());
                                current.Type = NodeType.Operation;
                                break;
                            case '=':
                                if (strExp[i + 1] != '=') throw GetFormatException();
                                i++;
                                current.OpCode = OpCodes.Equal;
                                current.Type = NodeType.Condition;
                                break;
                            case '!':
                                if (strExp[i + 1] != '=') throw GetFormatException();
                                i++;
                                current.OpCode = OpCodes.NotEqual;
                                current.Type = NodeType.Condition;
                                break;
                            case '>':
                                if (strExp[i + 1] == '=')
                                {
                                    i++;
                                    current.OpCode = OpCodes.GreaterThanOrEqual;
                                }
                                else
                                {
                                    current.OpCode = OpCodes.GreaterThan;
                                }
                                current.Type = NodeType.Condition;
                                break;
                            case '<':
                                if (strExp[i + 1] == '=')
                                {
                                    i++;
                                    current.OpCode = OpCodes.LessThanOrEqual;
                                }
                                else
                                {
                                    current.OpCode = OpCodes.LessThan;
                                }
                                current.Type = NodeType.Condition;
                                break;
                            case ':':
                            case '?':
                                current.Text = c.ToString();
                                current.OpCode = GetOpCode(c.ToString());
                                current.Type = NodeType.Condition;
                                break;
                            case '(':
                                {
                                    i++;
                                    int leftCount = 1, rightCount = 0, len = 0;
                                    int origin = i;

                                    while (leftCount != rightCount)
                                    {
                                        c = strExp[i];
                                        if (c == '(')
                                        {
                                            leftCount++;
                                            len++;
                                        }
                                        else if (c == ')')
                                        {
                                            rightCount++;
                                            if (leftCount == rightCount) break;
                                            len++;
                                        }
                                        else
                                        {
                                            len++;
                                        }
                                        i++;
                                        if (i >= strExp.Length) break;
                                    }
                                    if (leftCount != rightCount || len == 0) throw GetFormatException();
                                    current.Text = strExp.Substring(origin, len);
                                    current.Type = NodeType.StringExpression;
                                }
                                break;
                        }
                }

                return current.FirstNode;
            }

            private OpCodes GetOpCode(string text)
            {
                if (string.IsNullOrEmpty(text))
                    throw new ArgumentException("Text can not be empty.");
                switch (text)
                {
                    case "*": return OpCodes.Multiply;
                    case "/": return OpCodes.Divide;
                    case "%": return OpCodes.Modulo;
                    case "+": return OpCodes.Add;
                    case "-": return OpCodes.Subtract;
                    case "==": return OpCodes.Equal;
                    case "!=": return OpCodes.NotEqual;
                    case ">": return OpCodes.GreaterThan;
                    case ">=": return OpCodes.GreaterThanOrEqual;
                    case "<": return OpCodes.LessThan;
                    case "<=": return OpCodes.LessThanOrEqual;
                    case "?": return OpCodes.QuestionMark;
                    case ":": return OpCodes.Colon;
                    default:
                        throw GetFormatException();
                }
            }


            private bool IsDigit(char c)
            {
                return (c >= 0x30 && c <= 0x39) || c == '.';
            }


            private Node FindNode(Node node, OpCodes[] codes)
            {
                while (node != null)
                {
                    Node current = node;
                    if (Array.Exists(codes, m => m == current.OpCode))
                        return node;
                    node = node.Next;
                }
                return node;
            }

            #endregion

            private FormatException GetFormatException()
            {
                return new FormatException(string.Format("Invalid expression '{0}'。", m_Parent.ExpressionText));
            }
        }

        #region Public members
        /// <summary>
        /// Create a new expression
        /// </summary>
        /// <param name="expressionText">Expression text</param>
        public ComputeExpression(string expressionText)
        {
            if (string.IsNullOrEmpty(expressionText))
                throw new ArgumentNullException();
            ExpressionText = expressionText.Trim();
        }

        /// <summary>
        /// Compute value
        /// </summary>
        /// <returns>Result</returns>
        public T Execute<T>() where T : struct
        {
            var parser = new Parser<T>(this);
            Expression expression = parser.Parse();
            Func<T> invoker = Expression.Lambda<Func<T>>(expression).Compile();
            return invoker.Invoke();
        }

        public object Execute(Type type)
        {
            if (type == null) throw new ArgumentNullException("type");
            var runner = GetType().GetMethod("Execute", BindingFlags.Public | BindingFlags.Instance, null, new Type[0] { }, null).MakeGenericMethod(type);
            return runner.Invoke(this, null);
        }

        public string ExecuteBigInt()
        {
            var type = Type.GetType("System.Numeric.BigInteger, System.Core, Version=3.5.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089");
            return Execute(type).ToString();
        }

        public override string ToString()
        {
            return ExpressionText;
        }

        public string ExpressionText
        {
            get;
            private set;
        }
        #endregion

    }
}
